package DataStructure.graph;

import DataStructure.linear.Queue;

public class BreadthFirstSearch {
    private boolean[] marked;
    private int count;
    //用来存储待搜索邻接表的点
    private Queue<Integer> waitSearch;

    public BreadthFirstSearch(Graph G,int s){
        this.marked=new boolean[G.V()];
        this.count=0;
        this.waitSearch=new Queue<Integer>();
        bfs(G,s);
    }

    //使用广度优先搜索找出G图中v顶点的所有相邻顶点
    public void bfs(Graph G,int v){
        //把当前结点v标识为已搜索
        marked[v]=true;
        //让顶点v进入队列，带搜索
        waitSearch.enqueue(v);
        //通过循环，如果不为空则弹出一个待搜索的元素进行搜索
        while (!waitSearch.isEmpty()){
            Integer wait = waitSearch.dequeue();
            //遍历wait顶点的邻接表
            for (Integer w : G.adj(wait)) {
                if(!marked[w]){
                    bfs(G,w);
                }
            }
        }
        //让形同的顶点加一
        count++;
    }

    //判断w是否与s想通
    public boolean marked(int w){
        return marked[w];
    }

    //获取与s顶点想通的顶点总数
    public int count(){
        return count;
    }
}
